package leetcode;

/**
 * @author Liangyaoyun
 */
public class leetCode1985 {
    private void mergeSort(String[] nums){
        String[] numsSorted=new String[nums.length];
        mergeSortInner(nums,numsSorted,0, nums.length-1);
    }

    public void mergeSortInner(String[] nums,String[] numsSorted,int left,int right){
        if (left==right){
            return;
        }
        int mid=(left+right)/2;
        int i=left;
        int j=mid+1;
        int k=left;

        mergeSortInner(nums,numsSorted,left,mid);
        mergeSortInner(nums,numsSorted,mid+1,right);

        while (i<=mid&&j<=right){
            if (compare(nums[i],nums[j])){
                numsSorted[k]=nums[j];
                j++;
            }else {
                numsSorted[k]=nums[i];
                i++;
            }
            k++;
        }
        while (i<=mid){
            numsSorted[k]=nums[i];
            i++;
            k++;
        }
        while (j<=right){
            numsSorted[k]=nums[j];
            j++;
            k++;
        }
        for (int l = left; l <=right ; l++) {
            nums[l]=numsSorted[l];
        }
    }
    public boolean compare(String a,String b){
        char[] A=a.toCharArray();
        char[] B=b.toCharArray();
        int strA = 0,strB=0;
        if (A.length>B.length){
            return true;
        }else if (A.length<B.length){
            return false;
        }else {
            for (int i = 0; i < a.length(); i++) {
                if (A[i]>B[i]){
                    return true;
                }else if (A[i]<B[i]){
                    return false;
                }
            }
        }
    return false;
    }
    public String kthLargestNumber(String[] nums, int k) {
        mergeSort(nums);
        return nums[nums.length-k];
    }

    public static void main(String[] args) {
        String[] nums=new String[]{"423","521","2","42"};
        leetCode1985 leetCode1985=new leetCode1985();
        leetCode1985.mergeSort(nums);
    }
}
